package Datastruct.Hufffman;

import java.lang.reflect.Array;
import java.nio.charset.StandardCharsets;
import java.util.*;

public class HuffmanCodes {
    /**
     * 1.需要统计字母出现的次数
     * 2.创建赫夫曼树
     * 3.获取赫夫曼编码
     * 4.数据压缩
     **/

    //存储叶子结点路径
    private static Map<Byte, String> huffmanCode = new HashMap<>();
    //拼接赫夫曼编码
    private static StringBuilder stringBuilder = new StringBuilder();

    public static void main(String[] args) {

        String string = "I'm hanguoqing. What's your name";
        byte[] bytes = string.getBytes();
        List<NodeCode> nodeCodeList = getNodecodeWeight(bytes);
        System.out.println(nodeCodeList);

        NodeCode huffmantree = createHuffmanTree(nodeCodeList);
        Map<Byte, String> huffmancode = createHuffmancode(huffmantree);

        System.out.println("生成的赫夫曼编码是：" + huffmancode);

        byte[] zip = zip(bytes, huffmancode);
        System.out.println("压缩后的数组是：" + Arrays.toString(zip));

        float p = ((float) bytes.length - (float) zip.length) / (float) bytes.length;
        System.out.println("压缩比例为：" + p);

        String string1 = byteToString(true, (byte) -1);
        System.out.println(string1);

        byte[] decode = deCode(huffmancode, zip);
        System.out.println(new String(decode));


    }

    /*
     *1.统计字符串出现的次数
     * 返回集合{Node{data=32,weight=4}}
     * */
    public static List<NodeCode> getNodecodeWeight(byte[] bytes) {

        List<NodeCode> nodeCodes = new ArrayList<>();

        //每一个byte出现的次数，使用一个map集合  key=byte，value=weight
        Map<Byte, Integer> counts = new HashMap<>();
        //统计每个字符出现的次数
        for (byte abyte : bytes) {
            Integer count = counts.get(abyte);
            if (count == null) {
                counts.put(abyte, 1);
            } else {
                counts.put(abyte, count + 1);
            }
        }

        //将每一个map对象转换Node对象，存放在集合中
        for (Map.Entry<Byte, Integer> entry : counts.entrySet()) {
            nodeCodes.add(new NodeCode(entry.getKey(), entry.getValue()));
        }

        return nodeCodes;

    }

    /**
     * 创建赫夫曼树
     */
    public static NodeCode createHuffmanTree(List<NodeCode> nodeCodes) {

        while (nodeCodes.size() > 1) {
            //排序
            Collections.sort(nodeCodes);

            NodeCode leftnode = nodeCodes.get(0);
            NodeCode rightnode = nodeCodes.get(1);

            NodeCode newroot = new NodeCode(leftnode.weight + rightnode.weight);

            newroot.left = leftnode;
            newroot.right = rightnode;

            nodeCodes.remove(leftnode);
            nodeCodes.remove(rightnode);

            nodeCodes.add(newroot);

        }
        return nodeCodes.get(0);
    }

    /**
     * 获取赫夫曼编码
     * 1. 往左取0，往右取1
     * a：101
     * b：01000
     * <p>
     * 完整赫夫曼编码   10101000
     * StringBuilder  codes：用来拼接完整的赫夫曼编码
     * map永安路存取叶子结点路径  key=32   value 101   （32,101）（33,01000）
     */

    public static void getHuffmanCode(NodeCode nodeCode, String code, StringBuilder stringBuilder) {

        StringBuilder newString = new StringBuilder(stringBuilder);
        newString.append(code);

        if (nodeCode != null) {
            if (nodeCode.data == null) {
                //向左递归
                getHuffmanCode(nodeCode.left, "0", newString);

                //向右递归
                getHuffmanCode(nodeCode.right, "1", newString);
            } else {
                //如果是叶子结点，直接添加key，value
                huffmanCode.put(nodeCode.data, newString.toString());
            }
        }
    }

    /**
     * 设置统一入口
     */

    public static Map<Byte, String> createHuffmancode(NodeCode root) {
        if (root == null) {
            return null;
        }
        //先处理左子树
        getHuffmanCode(root.left, "0", stringBuilder);

        //处理右子树
        getHuffmanCode(root.right, "1", stringBuilder);

        return huffmanCode;
    }

    /**
     * 数据压缩
     * 01100011 0000101. ..........
     */

    public static byte[] zip(byte[] bytes, Map<Byte, String> huffmanCode) {

        //用来拼接所有叶子结点的路径
        StringBuilder stringBuilder = new StringBuilder();
        for (byte b : bytes) {
            stringBuilder.append(huffmanCode.get(b));
        }
        System.out.println("拼接后的哈夫曼编码是：" + stringBuilder.toString());
        int length;
        if (stringBuilder.length() % 8 == 0) {
            length = stringBuilder.length() / 8;
        } else {
            length = stringBuilder.length() / 8 + 1;
        }
        //压缩数据的数组
        byte[] huffmanbytes = new byte[length];

        int index = 0;
        for (int i = 0; i < stringBuilder.length(); i += 8) {
            String str;
            if (i + 8 > stringBuilder.length()) {
                str = stringBuilder.substring(i);
            } else {
                str = stringBuilder.substring(i, i + 8);
            }
            huffmanbytes[index] = (byte) Integer.parseInt(str, 2);
            index++;
        }
        return huffmanbytes;
    }

    /**
     * 数据解压过程
     * 1.首先把压缩数组转成赫夫曼编码，赫夫曼编码可以使用字符串进行接收拼接
     * 2.得到赫夫曼编码，转二进制
     * <p>
     * <p>
     * ***文本----》二进制数组-----》赫夫曼编码----》二进制字符串----》压缩数组
     * 数据解压
     * [-52, -72, 5, 110, -73, -94, -81, -16, 61, -42, -107, 124, 100, 78, 0]
     */


    //转为二进制字符串         8位
    public static String byteToString(boolean isRepair, byte b) {

        /*
         * b:占8个二进制为
         * int  :占32个二进制位
         *
         * 一个字节8位  int4个字节
         * */
        int temp = b;

        if (isRepair) {
            //按位与
            temp |= 256;    //256   10000000 | 00000001=10000001
        }
        String string = Integer.toBinaryString(temp);
        //返回的是补码
        if (isRepair) {
            return string.substring(string.length() - 8);
        } else {
            return string;
        }

    }

    /**
     * @param huffmanCode
     * @param huffmanBytes
     * @return 97  :1010    1010:97
     * <p>
     * 集合中原来是键的变为值  值变为键
     */
    public static byte[] deCode(Map<Byte, String> huffmanCode, byte[] huffmanBytes) {
        StringBuilder stringBuilder = new StringBuilder();
        for (int i = 0; i < huffmanBytes.length; i++) {

            byte b = huffmanBytes[i];
            boolean flg = false;
            if (i == huffmanBytes.length - 1) {
                flg = true;
            }

            stringBuilder.append(byteToString(!flg, b));
        }
        //键值转换
        Map<String, Byte> map = new HashMap<>();
        for (Map.Entry<Byte, String> entry : huffmanCode.entrySet()) {
            map.put(entry.getValue(), entry.getKey());
        }

        List<Byte> bytes = new ArrayList<>();
        for (int i = 0; i < stringBuilder.length(); ) {
            int count = 1;
            boolean flg = true;
            Byte b = null;
            while (flg) {
                String key = stringBuilder.substring(i, i + count);
                b = map.get(key);
                if (b == null) {
                    count++;
                } else {
                    flg = false;
                }

            }
            bytes.add(b);
            i += count;

        }

        byte[] buff = new byte[bytes.size()];
        for (int i = 0; i < buff.length; i++) {
            buff[i] = bytes.get(i);
        }


        return buff;
    }


}
